#include <stack>
#include <vector>

using namespace std;
class Solution {
public:
  int trap(vector<int> &height) {
    int ret = 0;
    stack<int> s;
    for (int i = 0; i < height.size(); i++) {
      while (!s.empty() && height[i] > height[s.top()]) {
        int r = s.top();
        s.pop();
        if (s.empty()) {
          break;
        }
        int l = s.top();
        int width = i - l - 1;
        int h = min(height[i], height[l]) - height[r];
        ret += width * h;
      }
      s.push(i);
    }
    return ret;
  }
};
